package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  归并排序  就是将大数组分成多个小数组 对小数组进行排序 在对结果进行合并
 *
 *  递归实现拆分 利用临时数组实现合并
 *
 *  时间复杂度 O(nlogn)
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] arr = {2,35,65,123,6,7,12,1};

        System.out.println(Arrays.toString(arr));

        arr = sort(arr);

        System.out.println(Arrays.toString(arr));

    }

    /**
     *  递归排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr){

        // 结束条件
        if(arr.length < 2){
            return arr;
        }

        // 拆分数组
        int[] left = Arrays.copyOfRange(arr, 0, arr.length/2);

        int[] right = Arrays.copyOfRange(arr, arr.length/2, arr.length);

        return merge(sort(left), sort(right));
    }

    /**
     *  按顺序合并两个数组
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] merge(int[] arr1, int[] arr2){
        int[] temp = new int[arr1.length + arr2.length];
        int i = 0;
        int j = 0;
        int x = 0;
        while (i < arr1.length || j < arr2.length){
            int v;
            if(i >= arr1.length){
                v = arr2[j++];
            }else if (j >= arr2.length){
                v = arr1[i++];
            }else if(arr1[i] > arr2[j]){
                v =  arr2[j++];
            }else {
                v =  arr1[i++];
            }
            temp[x++] = v;
        }
        return temp;
    }


}
